플로이드 워셜 알고리즘 - 그래프 모든 정점에서의 최단경로

parent link: 0011 Algorithms ♾️


플로이드 워셜 알고리즘 - 그래프 모든 정점에서의 최단경로


상태: 정리완료
태그: dp, graph

가중 그래프의 모든 꼭짓점 쌍에 대한 최단경로의 길이를 구해낼 수 있다. 경유 가능한 지점을 하나씩 추가해 가면서 최소값만을 dp에 갱신하는 것으로 구현이 가능하다.

graph LR
	i --> k
  k --> j
  i --> j

pseudo code

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each edge (u,v)
   dist[u][v] ← w(u,v)  // 변 (u,v)의 가중치
for each vertex v
   dist[v][v] ← 0
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][j] > dist[i][k] + dist[k][j]
            dist[i][j] ← dist[i][k] + dist[k][j]
        end if

시간복잡도

O(N3) 각 쌍을 탐색하는 데 O(N2), k가 1~n-1까지 변하므로 O(N)

연관문제

2617 구슬찾기 {boj} {플로이드워셜}